//给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。 
//
// 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。 
//
// 
//
// 示例 1： 
//
// 
//输入：[1, 2, 2, 3, 1]
//输出：2
//解释：
//输入数组的度是2，因为元素1和2的出现频数最大，均为2.
//连续子数组里面拥有相同度的有如下所示:
//[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
//最短连续子数组[2, 2]的长度为2，所以返回2.
// 
//
// 示例 2： 
//
// 
//输入：[1,2,2,3,1,4,2]
//输出：6
// 
//
// 
//
// 提示： 
//
// 
// nums.length 在1到 50,000 区间范围内。 
// nums[i] 是一个在 0 到 49,999 范围内的整数。 
// 
// Related Topics 数组 哈希表 
// 👍 378 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class DegreeOfAnArray {
    public static void main(String[] args) {
        Solution solution = new DegreeOfAnArray().new Solution();
        solution.findShortestSubArray(new int[]{1, 2, 2, 3, 1});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 查找数组的度就需要遍历一次了，添加到map当中去，然后找出出现次数最多的元素以及次数
     * 子串的话一定会包含所有的出现次数最多的元素之一（可能不只有一个）
     * 我的思路是这样的（测试案例倒是没有问题，提交之后超时了，这样真的没有问题）
     *      1.首先遍历数组，使用map记录各个元素出现的次数
     *      2.遍历map得到出现最多的值，因为可能不止有一个值，所以我用set来记录的，同时得到数组的度为max
     *      3.可能的子串最小长度为max，所以可以将max作为小数组的长度进行遍历
     *        而且子串一定包含出现频次最高的元素之一，所以再对不同出现频次最高的元素进行遍历统计其在子串中出现的次数
     *        如果出现次数达到了max，则直接将当前字串的长度返回就行了
     *
     */
    public int myFindShortestSubArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int max = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();
        for (int num : map.keySet()){
            if (map.get(num)>max){
                set.clear();
                max = map.get(num);
                set.add(num);
            }else if (map.get(num) == max){
                set.add(num);
            }
        }

        for (int i = max; i <= nums.length ; i++) {
            for (int num : set){
                for (int j = 0; j <= nums.length -i; j++) {
                    int count = 0;
                    for (int k = j; k < i+j ; k++) {
                        if (nums[k] == num) count++;
                    }
                    if (count == max) return i;
                }
            }
        }
        return 0;
    }

    /**
     * 题解中的算法：非常的巧妙
     * 求数组的度没什么好说的，还是使用map来实现
     * 但是求度的时候，同时进行了元素位置的记录，记录元素的初始位置和终止位置，只需要知道这两个位置就可以求最短的数组长度
     * 比如1 2 2 3 1
     * 元素1和2都是出现频次最高的数
     *      1的初始下标为0，终止下标为4，所以最短子串长度为4-0+1=5
     *      2的初始下标为1，终止下标为2，所以最短子串长度为2-1+1=2
     * map的value为int[]数组的话就方便多了，一次遍历直接添加了所有需要的内容
     */
    public int findShortestSubArray(int[] nums) {
        //定义一个Map，Key为数组中的值，Value为一个数组
        // 数组的第一个元素为Key出现的次数，第二个元素为Key第一次出现的位置，第三个元素为Key最后一次出现的位置。
        // map中的value为数组时可以不指定长度？
        Map<Integer,int[]> map = new HashMap<Integer,int[]>();
        int n = nums.length;
        //遍历数组，将每一个元素出现的次数、第一次出现的位置、最后一次出现的位置记录下来
        for(int i = 0;i<n;i++){
            if(map.containsKey(nums[i])){//说明当前元素不是第一次出现了
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            }else{//元素是第一次出现
                map.put(nums[i],new int[]{1,i,i});
            }
        }

        int maxNum = 0;
        int minLen = 0;

        //遍历Map,寻找出现最多次数的Key,若Key出现的次数相同，则选择长度较短的。
        for(Map.Entry<Integer, int[]> entry : map.entrySet()){
            int[] temp = entry.getValue();
            if(temp[0] > maxNum){
                maxNum = temp[0];
                minLen = temp[2]-temp[1]+1;
            }else if(temp[0] == maxNum){
                if(minLen > temp[2]- temp[1]+1){
                    minLen = temp[2]-temp[1]+1;
                }
            }
        }
        return minLen;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}